package org.algorithm.二师兄.链表;

import java.util.HashMap;
import java.util.Map;

/***
 * @author zhx
 * @Task 2022/2/21
 * @Link  {https://leetcode-cn.com/problems/lru-cache/}
 */
public class LRUCache {

    class ListNode{
        int key;
        int value;
        ListNode prev;
        ListNode next;
        public ListNode(){}
        public ListNode(int _key, int _value){
            this.key = _key;
            this.value = _value;
        }
    }

    private Map<Integer, ListNode> hashMap = new HashMap<>();
    // 长度
    private int size;
    // 容量
    private int capacity;
    // 指针
    private ListNode head, tail;

    // 构建双向空链表
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new ListNode();
        tail = new ListNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        ListNode listNode = hashMap.get(key);
        if (listNode == null) return -1;
        // 将value移动到头部
        moveVal2Head(listNode);
        return  listNode.value;
    }



    public void put(int key, int value) {
        ListNode listNode = hashMap.get(key);
        if (listNode == null) {
            ListNode newNode = new ListNode(key, value);
            hashMap.put(key, newNode);
            add2Head(newNode);
            ++size;
            if (size > capacity) {
                ListNode tail = removeTail();
                hashMap.remove(tail.key);
                --size;
            }
        }else {
            listNode.value = value;
            moveVal2Head(listNode);
        }
    }

    /**
     *  删除链表尾部
     * @return
     */
    private ListNode removeTail() {
        ListNode prev = tail.prev;
        removeNode(prev);
        return prev;
    }

    /***
     *  将节点放到链表头部
     * @param listNode
     */
    private void add2Head(ListNode listNode) {
        listNode.prev = head;
        listNode.next = head.next;
        head.next.prev = listNode;
        head.next = listNode;
    }

    // 删除当前链表头部
    private void removeNode(ListNode listNode) {
        listNode.prev.next = listNode.next;
        listNode.next.prev = listNode.prev;
    }

    /***
     *  将命中的元素移动的链表的头部
     * @param listNode
     */
    private void moveVal2Head(ListNode listNode) {
        removeNode(listNode);
        add2Head(listNode);
    }


    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(3);
        lruCache.put(1, 1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.put(4,4);
        System.out.println("lruCache.get(1) = " + lruCache.get(1));
        System.out.println("lruCache.get(1) = " + lruCache.get(2));
        System.out.println("lruCache.get(1) = " + lruCache.get(3));
        System.out.println("lruCache.get(1) = " + lruCache.get(4));
    }
}
